package dynamicProgramming.baseKnowledge;

/**
 * @author zxc
 * @date 2023/01/18 11:49
 **/

/**
 * 题目 ：爬楼梯的最少成本
 * 题目详述 ：
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 提示：
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 */
public class MinCostClimbingStairs_iteration {
    /**
     * 思路 ：迭代（即，从子问题开始解决，同时保存子问题解的结果，合并子问题解的结果，从而解决大问题）
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] redis = new int[length];
        // 迭代代码是从i = 2开始进行遍历的;
        // 所以一开始要对于redis[0],redis[1]进行赋值;
        redis[0] = cost[0];
        redis[1] = cost[1];
        // i的取值范围为[2 ， length - 1]
        // 即，for训话之后，redis数组中从下标为0到下标为length - 1都已经赋值;
        for(int i = 2 ; i < length ; i++){
            // 即，子问题结果逐步推算出大问题结果;（即，根据两个子问题f(i-1)和f(i-2)的解，来求解出f(i)的解）
            redis[i] = Math.min(redis[i - 1] , redis[i - 2]) + cost[i];
        }
        // 返回值
        return Math.min(redis[length - 1] , redis[length - 2]);
    }
}
